﻿#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    // 55. 跳跃游戏
    bool canJump(vector<int>& nums)
    {
        int left = 0, right = 0, maxPos = 0, n = nums.size();
        while (left <= right)
        {
            if (maxPos >= n - 1)
                return true;
            for (int i = left; i <= right; ++i)
                maxPos = max(maxPos, nums[i] + i);
            left = right + 1;
            right = maxPos;
        }
        return false;
    }

    // 134. 加油站
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
    {
        int n = gas.size();
        for (int i = 0; i < n; ++i) // 依次枚举所有起点
        {
            int res = 0; // 标记净收益
            int step = 0; // 标记走的步数
            for (; step < n; ++step)
            {
                int pos = (i + step) % n;
                res = res + gas[pos] - cost[pos];
                if (res < 0)
                    break;
            }
            if (res >= 0)
                return i;
            i = i + step;
        }
        return -1;
    }
};

int main()
{
    /*vector<int> v{ 2,3,1,1,4 };
    cout << Solution().canJump(v) << endl;*/

    vector<int> gas{ 1,2,3,4,5,5,70 };
    vector<int> cost{ 2,3,4,3,9,6,2 };
    cout << Solution().canCompleteCircuit(gas, cost) << endl;

    return 0;
}